#include <iostream>
#include <cassert>
#include <iomanip>
#include <stack>

using namespace std;

/*
1.把二元查找树转变成排序的双向链表
题目:
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。
    10
    /\
   /  \
  6   14
 /\    /\
4  8  12 16
转换成双向链表
4=6=8=10=12=14=16
*/

/***********树的定义**********************************/
struct BiTreeNode {
    int val;
    BiTreeNode* lchild;
    BiTreeNode* rchild;
};

typedef BiTreeNode* BSTPtr;

BSTPtr
buildBST(int array[], int n) {
    BSTPtr root = NULL;
    if (n == 0 || array == NULL)
        return NULL;

    for (int i = 0; i < n; ++i) {
        BSTPtr p = root, pre = NULL;
        while(p != NULL) {
            if (p->val > array[i]) 
                pre = p, p = p->lchild;
            else if (p->val < array[i])
                pre = p, p = p->rchild;
            else
                assert(false);
        }
        p = new BiTreeNode();
        p->val = array[i];
        p->lchild = p->rchild = NULL;
        if (pre == NULL) root = p;
        else {
            if (pre->val < p->val) pre->rchild = p;
            else pre->lchild = p;
        }
    }
    return root;
}

static void visit(BSTPtr p) {
    cout << p->val << setw(4);
}

// 非递归的中根遍历
void
InOrderVisit(BSTPtr root) {
    if (root == NULL)
        return;
    stack<BSTPtr> s;
    BSTPtr p = root;

    while(p != NULL || !s.empty()) {
        while(p != NULL) {
            s.push(p);
            p = p->lchild;
        }
        if (!s.empty()) {
            p = s.top();
            visit(p);
            s.pop();
            p = p->rchild;
        }
    }
}
/************************************************************/

struct LinkNode{
    int val;
    LinkNode* next;
    LinkNode* prev;
};

LinkNode*
convertBST2List(BSTPtr root) {
    LinkNode* head = NULL;
    LinkNode *pNode = NULL, *pNodePre = NULL;

    BSTPtr p = root;
    stack<BSTPtr> s;

    while(p != NULL || !s.empty()) {
        while(p!= NULL)
            s.push(p), p = p->lchild;
        if (!s.empty()) {
            p = s.top();
            pNode = new LinkNode();
            pNode->val = p->val;
            if (pNodePre == NULL) {
                head = pNode;
                head->next = NULL;
                head->prev = NULL;
            } else {
                pNodePre->next = pNode;
                pNode->prev = pNodePre;
            }
            pNodePre = pNode;
            s.pop();
            p = p->rchild;
        }
    }
    return head;
}

void printList(LinkNode* head) {
    LinkNode *p = head;
    while(p != NULL) {
        cout << p->val << setw(4);
        p = p->next;
    }
}



int main() {
    int array[] = {10, 6, 14, 4, 8, 12, 16};
    BSTPtr root = buildBST(array, sizeof(array) / sizeof(array[0]));
    InOrderVisit(root);
    std::cout << std::endl;
    LinkNode* head = convertBST2List(root);
    printList(head);
    std::cout << std::endl;
    return 0;
};
